package leetCode.q45;

public class Main1 {
    public int jump(int[] nums) {
        // 要到达的位置
        int position = nums.length - 1;

        int steps = 0;
        while (position >= 1) {
            //从头开始判断
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }

    public int jump1(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            //第i个结点能够访问到的最远的位置
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) { //可以一直走到end，而不用加次数；end之前不用花费步数，已经走到了最远处
                end = maxPosition;
                steps++;
            }
        }

        /*
        0: max=arr[0],end = arr[0],steps=1;
        1: max=
         */

        return steps;
    }
}
